#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "queue.h"
#include "log.h"
#include "tree.h"

struct _tree_node
{
    struct _tree_node *left;
    struct _tree_node *right;
    void *data;
};

struct _tree
{
    TreeNode *root;
    void (*free)(void *data);
    void (*print)(void *data);
    int (*compare)(void *lhs, void *rhs);
};

static int add_child_node(TreeNode *parent, TreeNode *node)
{
    if (!parent) return -1;
    if (!parent->left)
    {
        parent->left = node;
        return 0;
    }
    if (!parent->right)
    {
        parent->right = node;
        return 0;
    }
    return -1;
}

static TreeNode *find_void_child_node(Tree *tree)
{
    Queue *q = queue_new();
    TreeNode *tNode = tree->root;
    while(tNode != NULL)
    {
        if (!tNode->left || !tNode->right) goto find;
        queue_in(q, tNode->left);
        queue_in(q, tNode->right);
        tNode = (TreeNode *)(queue_out(q));
    }

find:
    queue_free(q);
    return tNode;
}

int tree_insert(Tree *tree, void *data)
{
    if (!data || !tree)
    {
        return -1;
    }

    TreeNode *parent = find_void_child_node(tree);
    TreeNode *node = malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    if (parent)
    {
        return add_child_node(parent, node);
    }
    else
    {
        tree->root = node;
    }
}

void tree_preorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    if (!node) return;
    visit(tree, node);
    tree_preorder_re(node->left, tree, visit);
    tree_preorder_re(node->right, tree, visit);
}

void tree_inorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    if (!node) return;
    tree_inorder_re(node->left, tree, visit);
    visit(tree, node);
    tree_inorder_re(node->right, tree, visit);
}

void tree_postorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    if (!node) return;
    tree_postorder_re(node->left, tree, visit);
    tree_postorder_re(node->right, tree, visit);
    visit(tree, node);
}

void tree_preorder(Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    Stack *s = stack_new();
    TreeNode *tNode = tree->root;
    while (stack_depth(s) != 0 || tNode)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            visit(tree, tNode);
            tNode = tNode->left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            tNode = tNode->right;
        }
    }

    stack_free(s);
}

void tree_inorder(Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    Stack *s = stack_new();
    TreeNode *tNode = tree->root;
    while(stack_depth(s) != 0 || tNode != NULL)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode->left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            visit(tree, tNode);
            tNode = tNode->right;
        }
    }
    stack_free(s);
}

void tree_postorder(Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    Stack *s = stack_new();
    TreeNode *tNode = tree->root;
    TreeNode *last_visit = NULL;
    while(tNode != NULL || !stack_is_empty(s))
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode->left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_top(s);
            if (tNode->right == NULL || tNode->right == last_visit)
            {
                stack_pop(s);
                last_visit = tNode;
                visit(tree, tNode);
                tNode = NULL;
            }
            else
            {
                tNode = tNode->right;
            }
            
        }
    }
    stack_free(s);
}

void tree_level_order(Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    Queue *q = queue_new();
    TreeNode *tNode = tree->root;
    while(tNode != NULL)
    {
        visit(tree, tNode);
        if (tNode->left)
            queue_in(q, tNode->left);
        if (tNode->right)
            queue_in(q, tNode->right);
        tNode = (TreeNode *)(queue_out(q));
    }
    queue_free(q);
}

static void treenode_free(Tree *tree, TreeNode *node)
{
    if (tree->free)
    {
        tree->free(node->data);
    }
    free(node);
}

static void treenode_print(Tree *tree, TreeNode *node)
{
    if (tree->print)
    {
        tree->print(node->data);
    }
}

void tree_empty(Tree *tree)
{
    tree_postorder_re(tree->root, tree, treenode_free);
    tree->root = NULL;
}

Tree *tree_new()
{
    return (Tree *)calloc(sizeof(Tree), 1);
}

void tree_free(Tree *t)
{
    tree_empty(t);
    free(t);
}

void int_print(void *data)
{
    int *p = (int *)data;
    printf("%d ", *p);
}

// #[test]
int tree_test()
{
    Tree *t = tree_new();
    int a = 1, b = 2, c = 3, d = 4, e = 5, f = 6, g = 7;
    tree_insert(t, &a);
    tree_insert(t, &b);
    tree_insert(t, &c);
    tree_insert(t, &d);
    tree_insert(t, &e);
    tree_insert(t, &f);
    tree_insert(t, &g);
    int root = *(int *)(t->root->data);
    int n1 = *(int *)(t->root->left->data);
    int n2 = *(int *)(t->root->right->data);
    printf("%d %d %d\n", root, n1, n2);
    t->print = int_print;
    debug("preorder recursive---");
    tree_preorder_re(t->root, t, treenode_print);
    println("");
    debug("preorder non-recursive---");
    tree_preorder(t, treenode_print);
    println("");
    debug("inorder recursive---");
    tree_inorder_re(t->root, t, treenode_print);
    println("");
    debug("inorder non-recursive---");
    tree_inorder(t, treenode_print);
    println("");
    debug("postorder recursive---");
    tree_postorder_re(t->root, t, treenode_print);
    println("");
    debug("postorder non_ecursive---");
    tree_postorder(t, treenode_print);
    println("");
    debug("level order---");
    tree_level_order(t, treenode_print);
    println("");
    tree_free(t);
    return 0;
}